<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3017：[Usaco2012 Nov]Cow Breeds</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2012 Nov]Cow Breeds</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2012 Nov]Cow Breeds</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2012 Nov]Cow Breeds                </h1>
                <p>时间限制：10s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div style="text-indent: 21pt"><span style="font-size: medium">Farmer John usually brands his cows with a circular mark, but his branding iron is broken, so he instead must settle for branding each cow with a mark in the shape of a parenthesis -- (. He has two breeds of cows on his farm: Holsteins and Guernseys. He brands each of his cows with a parenthesis-shaped mark. Depending on which direction the cow is facing, this might look like either a left parenthesis or a right parenthesis.</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium">FJ's N cows are all standing in a row, each facing an arbitrary direction, so the marks on the cows look like a string of parentheses of length N. Looking at this lineup, FJ sees a remarkable pattern: if he scans from left to right through just the Holsteins (in the order they appear in the sequence), this gives a balanced string of parentheses; moreover, the same is true for the Guernseys! To see if this is truly a rare event, please help FJ compute the number of possible ways he could assign breeds to his N cows so that this property holds.</span></div>
<div style="text-indent: 21pt"><span style="font-size: medium">There are several ways to define what it means for a string of parentheses to be &quot;balanced&quot;. Perhaps the simplest definition is that there must be the same total number of ('s and )'s, and for any prefix of the string, there must be at least as many ('s as )'s. For example, following strings are all balanced: </span></div>
<div><span style="font-size: medium">()</span></div>
<div><span style="font-size: medium">(())</span></div>
<div><span style="font-size: medium">()(()()) </span></div>
<div><span style="font-size: medium">while these are not: </span></div>
<div><span style="font-size: medium">)(</span></div>
<div><span style="font-size: medium">())(</span></div>
<div><span style="font-size: medium">((())))</span></div>
<div><span style="font-size: medium">&nbsp;</span></div>
<div><span style="font-size: medium">问题描述</span></div>
<div style="text-indent: 17.95pt"><span style="font-size: medium">给定一个长度为<i>n</i>的括号序列，每个要么是&rsquo;(&lsquo;，要么是&rsquo;)&rsquo;。你可以把每个位置的括号编号为H，或者是编号为G，要求编号后的括号序列所有编号为H的括号连在一起是合法的，所有编号为G的括号连在一起也是合法的。</span></div>
<div style="margin: 0cm 0cm 0pt 17.95pt"><span style="font-size: medium">其中：</span></div>
<div style="margin: 0cm 0cm 0pt 35.95pt; text-indent: -18pt"><span style="font-size: medium">①<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp; </span>()是合法的；</span></div>
<div style="margin: 0cm 0cm 0pt 35.95pt; text-indent: -18pt"><span style="font-size: medium">②<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp; </span>若<i>A</i>是合法的，则(<i>A</i>)是合法的；</span></div>
<div style="margin: 0cm 0cm 0pt 35.95pt; text-indent: -18pt"><span style="font-size: medium">③<span style="font: 7pt 'Times New Roman'">&nbsp;&nbsp;&nbsp;&nbsp; </span>若<i>A</i>，<i>B</i>都是合法的，则<i>AB</i>是合法的。</span></div>
<div><span style="font-size: medium">那么不同的编号方式有多少种？答案对2012取模。</span></div>
<div><span style="font-size: medium">&nbsp;</span></div></p><hr/><h3>输入格式</h3><p><div><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 一个长度为<i>n</i>的括号序列。</span></div>
<div><span style="font-size: medium">&nbsp;</span></div></p><hr/><h3>输出格式</h3><p><div>&nbsp;</div>
<div><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 不同的编号方式对2012取模后的值。</span></div>
<div><span style="font-size: medium">&nbsp;</span></div></p><hr/><h3>样例输入</h3><pre>
       (())
 </pre><hr/><h3>样例输出</h3><pre>
       6
 
样例说明
(())
HHHH
(())
GGGG
(())
HGGH
(())
GHHG
(())
HGHG
(())
GHGH
 
数据范围
       对于100%的数据满足：1 <= n <= 1,000。</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>Silver</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3017" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3017" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>